BOJ

[Silver V] 출입 기록 - 27111

문제 링크

성능 요약

메모리: 76408 KB, 시간: 524 ms

분류

구현, 시뮬레이션

제출 일자

2025년 8월 19일 22:44:33

문제 설명

위병소에서 근무하는 헌병은 오늘 근무를 끝마치고 보안 점검을 위해 출입 기록을 살펴보던 중, 오늘 출입 기록의 일부가 누락되었다는 사실을 깨달았다!

오늘 기록된 출입 기록은 총 $N$개이며, 출입 기록은 반드시 출입자가 출입한 시간순으로 기록된다.

 $i$번째 출입 기록은 두 개의 정수 $a_i,b_i$로 기록되는데, $a_i$는 출입하는 사람의 번호를 의미하며, $b_i$가 $1$이면 부대로 들어갔다는 뜻이고 $b_i$가 $0$이면 부대에서 나왔다는 뜻이다. 또한, 출입 기록을 시작하기 전과 출입 기록을 끝낸 후에는 부대 내에 아무도 없었다고 한다.

오늘의 출입 기록을 토대로 오늘 하루동안 누락된 출입 기록의 최소 개수를 구하여라.

입력

첫 번째 줄에 출입 기록의 개수 $N$이 주어진다. $(1\le N\le 200000)$ 

두 번째 줄부터 $N+1$번째 줄까지, $i$번째 출입 기록을 나타내는 정수 $a_i$와 $b_i$가 공백으로 구분되어 주어진다. $(1\le a_i\le 200000;$ $0\le b_i\le 1)$ 

출력

오늘 하루 동안 누락된 출입 기록의 최소 개수를 출력한다.

소스 코드

• 출입 기록.java